#include <iostream>
#include <sstream>
#include <fstream>
#include "stdafx.h"
#include "Solver.h"
#include "Settings.h"
#include <vector>
#include <algorithm>
#include <map>
#include <time.h>

using namespace std;

//Constructor
// argv: The command line arguments passed upon startup.
// argc: The number of elements in argv.
Solver :: Solver(int argc, char** argv)
{
	SettingsContainer = new Settings();
	SettingsContainer -> GetSettings(argc, argv);

	SettingsContainer -> WriteSettings();

	//Create a data structure representing the items, along with their value and costs,
	//and set the maximal cost.
	ReadData();
}

//A function that returns a vector of items with weight that is less than or equal to (LEQ) i.
vector<Item*>* Solver::FindItemsLEQI(int i)
{
	//Create a new empty vector.	
	vector<Item*>* Candidates = new vector<Item*>();

	//Cycle through all items.
	for(unsigned j = 0; j < Items->size(); ++j)
	{
		Item* it = Items->at(j);

		//If the cost of item j is less than or equal to i...
		if(it->Cost() <= i)
		{
			//Add it to the vector of items.
			Candidates->push_back(it);
		}
	}
	//Return the newly created vector.
	return Candidates;
}

// Serial method to solve the 0/1 Knapsack problem.
//
// The serial algorithm used here is described at http://en.wikipedia.org/wiki/Knapsack_problem. 
// It is in effect the following: A[i] = max(v_j + A[i-c_j] | c_j is less than or equal to i). 
// Note: It is assumed that for all items, the cost of the item is greater than zero.
int Solver :: Solve()
{
    //Allocate the Answers array.
	Answers = new Solution*[MaximumCost + 1];

    //Create an answer for zero weight that has zero value.
	Solution *CurrentMax = new Solution(0, 0, NULL, NULL);

	vector<Item*>* CandidateItems = NULL;

    //The zero value solution is initially the best solution.
	Answers[0] = CurrentMax;

	Solution *SubProblem = NULL;

	for(int i = 1; i <= MaximumCost; ++i)
	{
        //Get each item that can be considered at the current cost i.
		CandidateItems = FindItemsLEQI(i);

		//For each item that can be considered
		for(unsigned j = 0; j < CandidateItems->size(); ++j)
		{
			Item* it = CandidateItems->at(j);

			//Get the optimal sub-problem for the remaining cost alottment
			SubProblem = Answers[i - it->Cost()];

			//If the cost of it and the sub-problem is less than i...
			if(SubProblem->Cost() + it->Cost() <= i)
			{
                //If the value of it and the sub-problem is greater than the current maximum...
				if(CurrentMax->Value() <= (it->Value() + SubProblem->Value()))
				{
		            //Make sure the sub-problem does not already contain it (this is the 0/1 constraint)
					if(!SubProblem->ContainsItem(it->Number()))
					{
                        //The best solution so far has been found for cost i
						CurrentMax = new Solution(SubProblem->Cost() + it->Cost(), SubProblem->Value() + it->Value(), it, SubProblem);
					}
				}
			}
		}

		delete CandidateItems;

        //Once all solutions have been tried for cost i, the best overall solution (for cost i) is in CurrentMax.
        //Store this solution for cost i in Answers.
		Answers[i] = CurrentMax;
	}



	return 0;
}

//Input of results
void Solver::Finish(double time)
{

	printf("\r\n");
    printf("Clock time (sec): %.8f \r\n", time);  

        FILE* outputResult = 0;
        FILE* outputProfile = 0;

   if( fopen_s(&outputProfile, SettingsContainer->profileFile , "wb")) 
    {
        printf("Can't create profile file!\r\n");            
		fclose(outputProfile);
        return;
    }

    if( fopen_s(&outputResult, SettingsContainer->resultsFile , "wb")) 
    {
        printf("Can't create result file!\r\n");   
        fclose(outputResult);
        return;
    }

	fprintf(outputProfile, "#Dwarfname:%s\r\n",SettingsContainer->dwarfName);

        char tmpbuf[1024];
        _tzset();
        
        _strdate_s( tmpbuf, 1024 );
        fprintf(outputProfile, "#Time: %s ",tmpbuf);

        _strtime_s( tmpbuf, 1024 );
        fprintf(outputProfile, "%s \r\n",tmpbuf);

        fprintf(outputProfile, "#Result time (sec): %.8f\r\n", time);  

        fprintf(outputResult, "The optimal solution for cost %d is:\r\n", MaximumCost);
        fprintf(outputResult, "Cost: %d, Value: %d\r\n", Answers[MaximumCost]->Cost(), Answers[MaximumCost]->Value());
        fprintf(outputResult, "With elements being:\r\n");
		fprintf(outputResult, Answers[MaximumCost]->ToString().c_str());

        fclose(outputProfile);
        fclose(outputResult);


}

// Read the Item data, one Item value and associated cost per line, 
// into a list of Items.
//
//
// The first line of the file contains a single integer representing
// the maximum allowed cost C.
// The second line contains a single integer representing the number of elements in the input file.
// Each subsequent line contains two integer values for a given item: 
// 1) item cost, and
// 2) item value.
void Solver::ReadData()
{
	ifstream inf;

    //Open the file.
	inf.open(SettingsContainer -> inputFile, ios::in);

	//If there is an error then print a useful message and terminate.
	if(!inf)
	{
		cout << "The file " << SettingsContainer -> inputFile << " could not be found." << endl;
		exit(1);
	}

    //Set the maximum cost for the solver.
	inf >> MaximumCost;

    //Set the number of items in the file.
	inf >> ItemCount;

	Items = new vector<Item*>();

    //For each remaining line in the file:
	for(int i = 0; i < ItemCount; ++i)
	{
        //Create a new item with the associated cost and value of the given line
        //cost, value
		int cost;
		int value;
		string coma;
		inf >> cost;
		inf >> coma;
		inf >> value;
		Items->push_back(new Item(cost, value, i));
	}

    //Close the file.
	inf.close();

}

Item::Item()
{
	myCost = 0;
	myValue = 0;
	myNumber = 0;
}
Item::Item(int cost, int value, int number)
{
	myCost = cost;
	myValue = value;
	myNumber = number;
}
// Format the Item's data in a string.
string Item::ToString()
{
	stringstream out;
	out << myNumber << ": " << myCost << ", " << myValue;
	return out.str();
}
Solution::Solution()
{
	myCost = 0;
	myValue = 0;
	myItem = 0;
	mySubSolution = 0;
}

Solution::Solution(int cost, int value, Item* item, Solution* subSolution)
{
	myCost = cost;
	myValue = value;
	myItem = item;
	mySubSolution = subSolution;
}

// Format the data within this solution as a string.
string Solution::ToString()
{
	vector<Item> items;
	Solution *solution = this;
	while (solution != NULL) {
		if (solution->myItem != NULL)
			items.push_back(*(solution->myItem));
		solution = solution->mySubSolution;
	}
	sort(items.begin(), items.end());

	stringstream out;
	for (vector<Item>::iterator i = items.begin(); i != items.end(); i++) {
		out << i->ToString() << "\r\n";
	}
	return out.str();
}

// Tests whether this solution contains an item labeled with itemNumber.
// Returns true if an Item with the specified itemNumber is part of this solution.  False otherwise.
bool Solution::ContainsItem(int itemNumber)
{
	bool returnValue = false;
	//If I have an item...
	if(myItem != NULL)
	{
        //check to see whether itemNumber is my Item...
		if(myItem->Number() == itemNumber)
		{
            //if so -- return true
			returnValue = true;
		}
		else
		{
            //if not -- check mySubSolution to see if itemNumber is used there.
			if(mySubSolution != NULL)
			{
				returnValue = mySubSolution->ContainsItem(itemNumber);
			}
		}
	}
	return returnValue;
}

